#include "binaryTree.h"

void
PreOrder(BTNode* root)
{
  if (root == NULL) {
    return;
  }
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}

void
InOrder(BTNode* root)
{
  if (root == NULL) {
    return;
  }
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}

void
PostOrder(BTNode* root)
{
  if (root == NULL) {
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}

int
TreeSize(BTNode* root)
{
  return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}

int
TreeLeaf(BTNode* root)
{
  if (!root) {
    return 0;
  }

  if (root->left == NULL && root->right == NULL) {
    return 1;
  }

  return TreeLeaf(root->left) + TreeLeaf(root->right);
}

int
TreeHeight(BTNode* root)
{
  if (root == NULL) {
    return 0;
  }
  int leftHeight = TreeHeight(root->left);
  int rightHeight = TreeHeight(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int
TreeKSize(BTNode* root, int k)
{
  if (root == NULL)
    return 0;

  if (k == 1)
    return 1;

  return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}

BTNode*
TreeFind(BTNode* root, int x)
{
  if (!root)
    return NULL;

  if (root->value == x)
    return root;

  BTNode* res = NULL;

  if (res = TreeFind(root->left, x))
    return res;

  if (res = TreeFind(root->right, x))
    return res;

  return NULL;
}

bool
isUnivalTree(BTNode* root)
{
  if (root == NULL) {
    return true;
  }
  if (root->left && root->left->val != root->val) {
    return false;
  }
  if (root->right && root->right->val != root->val) {
    return false;
  }
  return isUnivalTree(root->left) && isUnivalTree(root->right);
}

bool
isSameTree(BTNode* p, BTNode* q)
{
  if (!p && !q) {
    return true;
  }
  if (!p || !q) {
    return false;
  }
  if (p->val != q->val) {
    return false;
  }

  // 不用比较左右孩子 ~
  // if ((p->left && q->left) && (p->left->val != q->left->val)) {
  //   return false;
  // }
  // if ((p->right && q->right) && (p->right->val != q->right->val)) {
  //   return false;
  // }

  return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool
isSubtree(BTNode* root, BTNode* subRoot)
{
  if (!root && !subRoot)
    return true;
  if (!root || !subRoot)
    return false;
  if (isSameTree(root, subRoot))
    return true;
  return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

BTNode*
reBuildBinaryTree(char* str, int* pi)
{
  if (str[*pi] == '#') {
    (*pi)++;
    return NULL;
  }

  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  root->val = str[(*pi)++];
  root->left = reBuildBinaryTree(str, pi);
  root->right = reBuildBinaryTree(str, pi);

  return root;
}